Ciągi bez zająknięć
Limit pamięci: 32 MB
Rozważamy ciągi liter.
Powiemy, że ciąg zawiera zająknięcie,
jeśli napotykamy w nim dwa, następujące bezpośrednio po sobie,
wystąpienia takiego samego podciągu.
Tzn. jeśli dla pewnych i ()
zachodzi: .
Interesują nas -elementowe ciągi bez zająknięć
o minimalnej liczbie liter.
Przykład
Dla wystarczą dwie litery, powiedzmy i .
Mamy dokładnie dwa 3-elementowe ciągi bez zająknięć złożone
z takich liter: i .
Dla potrzebne są już 3 różne litery.
Na przykład
jest trójliterowym ciągiem bez zająknięć.
W ciągu mamy dwa zająknięcia: i .
Zadanie
Napisz program, który:
-
wczyta długość ciągu ,
-
obliczy -elementowy ciąg bez zająknięć o minimalnej
liczbie różnych liter,
-
wypisze wynik.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest
jedna dodatnia liczba całkowita , .
Wyjście
Twój program powinien pisać na standardowe wyjście.
W pierwszym wierszu powinna zostać wypisana
jedna dodatnia liczba całkowita ,
równa minimalnej liczbie różnych liter, które muszą wystąpić
w -elementowym ciągu nie zawierającym zająknięć.
W drugim wierszu należy wypisać obliczony ciąg bez zająknięć, jako
słowo złożone z małych liter alfabetu angielskiego,
od litery do -tej litery alfabetu.
Jeżeli istnieje wiele takich ciągów, Twój program powinien wypisać
jeden z nich.
Możesz przyjąć, że 26 liter wystarczy.
Przykład
Dla danych wejściowych:
5
poprawną odpowiedzią jest:
3
abcab
Autor zadania: Krzysztof Sikora.